#include <ctime>
#include <chrono>

#include <string>
#include <cstring>

#include <queue>
#include <iostream>
#include <algorithm>

#include <memory>
#include <concepts>
#include <stdexcept>
#include <functional>
#include <type_traits>

using namespace std;

template <typename _Kty, class _Alg = void, typename Enable = void>
struct Context;

template <typename _Kty, class _Pr = less<_Kty> >
requires regular_invocable<_Pr, const _Kty &, const _Kty &>
struct SortBase{
    // end contains no element

    using value_type = _Kty;
    using key_compare = _Pr;

    inline void operator () (_Kty *begin, _Kty *end) const {
        this -> sort(begin, end);
    }
    inline void operator () (Context<_Kty, void, void> context) const {
        this -> sort(context);
    }

    virtual void sort(_Kty *begin, _Kty *end) const = 0;
    inline void sort(Context<_Kty, void, void> context) const {
        this -> sort(context.begin(), context.end());
    }

    void make_a_test(size_t n) const{
        cout << "this is: " << whoami() << " test size " << n << endl;
        _Kty *a = new _Kty[n];
        generate_n(a, n, [](){ return rand() - rand(); });
        unsigned long long s, t;
        s = chrono::steady_clock::now().time_since_epoch().count();
        try{
            this -> sort(begin, end);
            t = chrono::steady_clock::now().time_since_epoch().count();
            for (int i = 0; i < n - 1; i++)
                if (a[i] > a[i + 1])
                    throw logic_error("Sort Error!");
            cout << "Time spent: " << t - s << endl;
        }
        catch (runtime_error &e){
            cout << e.what() << endl;
        }
        delete[] a;
    }

    inline string whoami() const {
        return typeid(*this).name();
    }

};

template <typename _Kty, class _Pr = less<_Kty> >
struct BubbleSort : SortBase<_Kty, _Pr>{
    void __sort(_Kty *begin, _Kty *end, _Pr cmp) const{
        for (_Kty *it1 = end; it1 != begin; it1--)
            for (_Kty *it2 = begin + 1; it2 != it1; it2++)
                if (cmp(*it2, *(it2 - 1)))
                    swap(*it2, *(it2 - 1));
    }
    void sort(_Kty *begin, _Kty *end) const{
        __sort(begin, end, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct InsertSort : SortBase<_Kty, _Pr>{
    void __sort(_Kty *begin, _Kty *end, _Pr cmp) const {
        for (_Kty *it1 = begin; it1 != end; it1++){
            _Kty *pos = upper_bound(begin, it1, *it1, cmp);
            for (_Kty *it2 = it1 - 1; it2 >= pos; it2--)
                swap(*(it2 + 1), *it2);
        }
    }
    void sort(_Kty *begin, _Kty *end) const {
        __sort(begin, end, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct ShellSort : SortBase<_Kty, _Pr>{
    void __sort(_Kty *s, int n, _Pr cmp) const{
        for (int g = n >> 1; g > 0; g >>= 1){
            g |= 1;
            for (int i = g; i < n; i++){
                int j = i;
                while (j >= g && cmp(s[j], s[j - g])){
                    swap(s[j], s[j - g]);
                    j -= g;
                }
            }
        }
    }
    void sort(_Kty *begin, _Kty *end) const{
        __sort(begin, end - begin, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct RandomQuickSort : SortBase<_Kty, _Pr>{
    void __sort(_Kty *a, int s, int t, _Pr cmp) const{
        if (s == t)
            return;
        int i = s, j = t;
        _Kty tmp, mid = a[rand() % (t - s) + s];
        while (i < j){
            while (cmp(a[i], mid))
                i++;
            while (cmp(mid, a[j]))
                j--;
            if (i <= j){
                tmp = a[i], a[i] = a[j], a[j] = tmp;
                i++, j--;
            }
        }
        if (s < j)
            __sort(a, s, j, cmp);
        if (i < t)
            __sort(a, i, t, cmp);
    }
    void sort(_Kty *begin, _Kty *end) const{
        __sort(begin, 0, end - begin - 1, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct MergeSort : SortBase<_Kty, _Pr>{
    void __sort(_Kty *a, int s, int t, _Kty *c, _Pr cmp) const{
        if (s == t)
            return;
        int mid = (s + t) >> 1;
        if (t - s >= 2){
            __sort(a, s, mid, c, cmp);
            __sort(a, mid + 1, t, c, cmp);
        }
        int i = s, j = mid + 1, k = 0;
        while (i <= mid && j <= t){
            if (cmp(a[i], a[j]))
                c[k++] = a[i++];
            else
                c[k++] = a[j++];
        }
        while (i <= mid)
            c[k++] = a[i++];
        while (j <= t)
            c[k++] = a[j++];
        memcpy(a + s, c, sizeof(int) * (t - s + 1));
    }
    void sort(_Kty *begin, _Kty *end) const{
        _Kty *c = new _Kty[end - begin];
        __sort(begin, 0, end - begin - 1, c, _Pr());
        delete[] c;
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct BinaryHeapSort : SortBase<_Kty, _Pr>{
    void Insert(_Kty *heap, int &tot, const _Kty &tar, _Pr cmp) const{
        int cur, fa;
        heap[++tot] = tar;
        cur = tot;
        while (cur > 1){
            fa = cur >> 1;
            if (cmp(heap[fa], heap[cur]))
                break;
            swap(heap[cur], heap[fa]);
            cur = fa;
        }
    }
    void Delete(_Kty *heap, int &tot, _Pr cmp) const{
        int cur, son;
        swap(heap[1], heap[tot--]);
        cur = 1;
        while ((son = cur << 1) <= tot){
            son ^= son < tot && heap[son ^ 1] < heap[son];
            if (cmp(heap[cur], heap[son]))
                break;
            swap(heap[cur], heap[son]);
            cur = son;
        }
    }
    void __sort(_Kty *begin, _Kty *end, _Pr cmp) const {
        int tot = 0;
        _Kty *heap = new _Kty[end - begin + 1];
        for (_Kty *it = begin; it != end; it++)
            Insert(heap, tot, *it, cmp);
        for (_Kty *it = begin; it != end; it++)
            Delete(heap, tot, cmp);
        reverse_copy(heap + 1, heap + (end - begin) + 1, begin);
        delete[] heap;
    }
    void sort(_Kty *begin, _Kty *end) const{
        __sort(begin, end, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty>, typename Enable = void>
struct RadixSort : SortBase<_Kty, _Pr> {};

template <typename _Kty>
struct RadixSort<_Kty, less<_Kty>,
    enable_if_t<sizeof(_Kty) == 4> >
    : SortBase<_Kty, less<_Kty> >{
    void __sort(unsigned n, unsigned *a, unsigned *b) const {
        unsigned r1[0x100], r2[0x100], r3[0x100], r4[0x100];
        memset(r1, 0, sizeof(r1)), memset(r2, 0, sizeof(r2));
        memset(r3, 0, sizeof(r3)), memset(r4, 0, sizeof(r4));

        unsigned i;
        unsigned tmp_int, *j, *tar;

        for (j = a, tar = a + n; j != tar; ++j){
            tmp_int = *j;
            ++r1[tmp_int & 0xff];
            ++r2[(tmp_int >> 0x8) & 0xff];
            ++r3[(tmp_int >> 0x10) & 0xff];
            ++r4[tmp_int >> 0x18];
        }
        for (i = 1; i <= 0xff; ++i){
            r1[i] += r1[i - 1];
            r2[i] += r2[i - 1];
            r3[i] += r3[i - 1];
            r4[i] += r4[i - 1];
        }
        for (j = a + n - 1; j != a - 1; --j)
            b[--r1[(*j) & 0xff]] = *j;
        for (j = b + n - 1; j != b - 1; --j)
            a[--r2[((*j) >> 0x8) & 0xff]] = *j;
        for (j = a + n - 1; j != a - 1; --j)
            b[--r3[((*j) >> 0x10) & 0xff]] = *j;
        for (j = b + n - 1; j != b - 1; --j)
            a[--r4[(*j) >> 0x18]] = *j;
    }
    void sort(_Kty *begin, _Kty *end) const {
        unsigned *b = new unsigned[end - begin];
        __sort(end - begin, reinterpret_cast<unsigned *>(begin), b);
        reverse(begin, end);
        reverse(begin, lower_bound(begin, end, 0));
        reverse(upper_bound(begin, end, 0), end);
        delete[] b;
    }
};

template <typename _Kty>
struct RadixSort<_Kty, less<_Kty>,
    enable_if_t<sizeof(_Kty) == 8> >
    : SortBase<_Kty, less<_Kty> >{
    void __sort(unsigned n, unsigned long long *a, unsigned long long *b) const {

        unsigned r1[0x10000], r2[0x10000], r3[0x10000], r4[0x10000];
        memset(r1, 0, sizeof(r1)), memset(r2, 0, sizeof(r2));
        memset(r3, 0, sizeof(r3)), memset(r4, 0, sizeof(r4));

        unsigned i;
        unsigned long long tmp_int, *j, *tar;

        for(j = a, tar = a + n; j != tar; ++j){
            tmp_int = * j;
            ++r1[tmp_int & 0xffff];
            ++r2[(tmp_int >> 0x10) & 0xffff];
            ++r3[(tmp_int >> 0x20) & 0xffff];
            ++r4[tmp_int >> 0x30];
        }
        for (i = 1; i <= 0xffff; ++i){
            r1[i] += r1[i - 1];
            r2[i] += r2[i - 1];
            r3[i] += r3[i - 1];
            r4[i] += r4[i - 1];
        }
        for(j = a + n - 1; j != a - 1; --j)
            b[r1[(* j) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r2[((* j) >> 0x10) & 0xffff]--] = *j;
        for(j = a + n - 1; j != a - 1; --j)
            b[r3[((* j) >> 0x20) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r4[(* j) >> 0x30]--] = *j;
    }
    void sort(_Kty *begin, _Kty *end) const {
        unsigned long long *b = new unsigned long long[end - begin];
        __sort(end - begin, reinterpret_cast<unsigned long long*>(begin), b);
        reverse(begin, end);
        reverse(begin, lower_bound(begin, end, 0));
        reverse(upper_bound(begin, end, 0), end);
        delete[] b;
    }
};

template <typename _Kty>
struct RadixSort<_Kty, less<_Kty>,
    enable_if_t<sizeof(_Kty) == 16 && _GLIBCXX_USE_INT128> >
    : SortBase<_Kty, less<_Kty> >{
    void __sort(unsigned n, __uint128_t *a, __uint128_t *b) const {
        unsigned r1[0x10000], r2[0x10000], r3[0x10000], r4[0x10000];
        unsigned r5[0x10000], r6[0x10000], r7[0x10000], r8[0x10000];
        memset(r1, 0, sizeof(r1)), memset(r2, 0, sizeof(r2));
        memset(r3, 0, sizeof(r3)), memset(r4, 0, sizeof(r4));
        memset(r5, 0, sizeof(r5)), memset(r6, 0, sizeof(r6));
        memset(r7, 0, sizeof(r7)), memset(r8, 0, sizeof(r8));
        
        unsigned i;
        __uint128_t tmp_int, * j, *tar;

        for(j = a, tar = a + n; j != tar; ++j){
            tmp_int = * j;
            ++r1[tmp_int & 0xffff];
            ++r2[(tmp_int >> 0x10) & 0xffff];
            ++r3[(tmp_int >> 0x20) & 0xffff];
            ++r4[(tmp_int >> 0x30) & 0xffff];
            ++r5[(tmp_int >> 0x40) & 0xffff];
            ++r6[(tmp_int >> 0x50) & 0xffff];
            ++r7[(tmp_int >> 0x60) & 0xffff];
            ++r8[tmp_int >> 0x70];
        }
        for(i = 1; i <= 0xffff; ++i){
            r1[i] += r1[i - 1];
            r2[i] += r2[i - 1];
            r3[i] += r3[i - 1];
            r4[i] += r4[i - 1];
            r5[i] += r5[i - 1];
            r6[i] += r6[i - 1];
            r7[i] += r7[i - 1];
            r8[i] += r8[i - 1];
        }
        for(j = a + n - 1; j != a - 1; --j)
            b[r1[(* j) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r2[((* j) >> 0x10) & 0xffff]--] = *j;
        for(j = a + n - 1; j != a - 1; --j)
            b[r3[((* j) >> 0x20) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r4[((* j) >> 0x30) & 0xffff]--] = *j;
        for(j = a + n - 1; j != a - 1; --j)
            b[r5[((* j) >> 0x40) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r6[((* j) >> 0x50) & 0xffff]--] = *j;
        for(j = a + n - 1; j != a - 1; --j)
            b[r7[((* j) >> 0x60) & 0xffff]--] = *j;
        for(j = b + n - 1; j != b - 1; --j)
            a[r8[(* j) >> 0x70]--] = *j;
    }
    void sort(_Kty *begin, _Kty *end) const {
        __uint128_t *b = new __uint128_t[end - begin];
        __sort(end - begin, reinterpret_cast<__uint128_t *>(begin), b);
        reverse(begin, end);
        reverse(begin, lower_bound(begin, end, 0));
        reverse(upper_bound(begin, end, 0), end);
        delete[] b;
    }
};

template <typename _Kty>
struct RadixSort<_Kty, greater<_Kty> > : SortBase<_Kty, greater<_Kty> >{
    void sort(_Kty *begin, _Kty *end) const {
        RadixSort<_Kty, less<_Kty>>()(begin, end);
        reverse(begin, end);
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct STDQuickSort : SortBase<_Kty, _Pr>{
    void sort(_Kty *begin, _Kty *end) const {
        std::sort(begin, end, _Pr());
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct STDMergeSort : SortBase<_Kty, _Pr>{
    void sort(_Kty *begin, _Kty *end) const {
        std::stable_sort(begin, end, _Pr());
    }
};


template <typename _Kty, typename _Pr>
struct binaryNegate : public binary_function<_Kty, _Kty, bool>{
    _Pr _M_pred = _Pr();
    _GLIBCXX14_CONSTEXPR bool operator() (const _Kty& __x, const _Kty& __y) const {
        return !_M_pred(__x, __y);
    }
};

template <typename _Kty, class _Pr = less<_Kty> >
struct STDPriorityQueueSort : SortBase<_Kty, _Pr>{
    void sort(_Kty *begin, _Kty *end) const {
        priority_queue<_Kty, vector<_Kty>, binaryNegate<_Kty, _Pr> > pq;
        for (int *it = begin; it != end; it++)
            pq.push(*it);
        for (int *it = begin; it != end; it++)
            *it = pq.top(), pq.pop();
    }
};

template <typename _Kty, class _Alg>
struct _Context {
public:
    using value_type = _Kty;

    _Context(value_type *_b, value_type *_e) : _begin(_b), _end(_e) {}

    inline value_type * begin() { return _begin; }
    inline value_type * end() { return _end; }
    inline string whoisin() const {
        return typeid(_Alg).name();
    }
protected:
    value_type *_begin = nullptr, *_end = nullptr;
};

template <typename _Kty, class _Alg, typename Enable>
struct Context : _Context<_Kty, _Alg> {};

template <class _Alg>
struct Context<typename _Alg::value_type, _Alg, 
    enable_if_t<derived_from<_Alg, SortBase<typename _Alg::value_type, typename _Alg::key_compare> > >> 
    : _Context<typename _Alg::value_type, _Alg>{
    // 静态算法，构造函数传入参数，通过Context.sort()实现
public:
    using value_type = typename _Alg::value_type;
    using key_compare = typename _Alg::key_compare;

    Context(value_type *_b, value_type *_e, const _Alg &_a = _Alg()) 
        : _Context<value_type, _Alg>(_b, _e), alg(_a) {}
    inline Context<value_type, void, void> convertTo(){
        return Context(_Context<value_type, _Alg>::begin(), _Context<value_type, _Alg>::end());
    }
    inline void sort() { alg.sort(_Context<value_type, _Alg>::begin(), _Context<value_type, _Alg>::end()); }
    inline void operator () () { this -> sort(); }

private:
    _Alg alg = _Alg();
};

template <typename _Kty>
struct Context<_Kty, void, void> : _Context<_Kty, void> {
    // 动态选择算法，通过Strategy(Context)实现
public:
    using value_type = _Kty;
    
    Context() {};
    Context(value_type *_b, value_type *_e) 
        : _Context<value_type, void>(_b, _e) {}
    template <typename _TAlg>
    inline Context<typename _TAlg::value_type, _TAlg, 
        enable_if_t<derived_from<_TAlg, SortBase<typename _TAlg::value_type, typename _TAlg::key_compare> > >> 
        convertTo(const _TAlg &target){
        return Context(_Context<value_type, void>::begin(), _Context<value_type, void>::end(), target);
    }
};

int main(){
    // srand(19491001);
    {
        int a[10] = {23, 42, 3, 23, 4, 5, 67, 10, 13, 15};
        Context<int> x(a, a + 10);
        STDPriorityQueueSort<int, greater<int> > y;
        y(x);
        cout << y.whoami() << endl;
        for (int i = 0; i < 10; i++){
            printf("%d%c", a[i], " \n"[i == 9]);
        }
    }
    {
        int a[10] = {114514, -1919810, 1123, -2323, 22332233, -1133, 1, 2, 3, 4};
        Context<int, RadixSort<int, less<int> > > y(a, a + 10);
        y.sort();
        cout << y.whoisin() << endl;
        for (int i = 0; i < 10; i++){
            printf("%d%c", a[i], " \n"[i == 9]);
        }
    }
    return 0;
}

